package search

/**
字符串匹配之 BF 算法(Brute Force)
作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，如果主串长度为 n，模式串长度为 m，
我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。如bf_search图所示

BF 算法的时间复杂度最差是 O(n*m)，意味着要模式串要移到主串 n-m 的位置上，并且模式串每个字符都要与子串比较
*/
func bfSearch(s, p string) int {
	begin := 0
	i, j := 0, 0
	n, m := len(s), len(p) // 主串、子串长度
	for i = 0; i < n; begin++ {
		// 通过 BF 算法暴力匹配子串和主串
		for j = 0; j < m; j++ {
			if i < n && s[i] == p[j] {
				// 如果子串和主串对应字符相等，逐一往后匹配
				i++
			} else {
				// 否则退出当前循环，从主串下一个字符继续开始匹配
				break
			}
		}
		if j == m {
			// 子串遍历完，表示已经找到，返回对应下标
			return i - j
		}
		// 从下一个位置继续开始匹配
		i = begin
		i++
	}
	return -1
}

// 基于 BF 算法实现字符串查找函数
func FindStringWithBFSearch(mainStr, subStr string) int {
	// 子串长度=0
	if len(subStr) == 0 {
		return 0
	}
	//主串长度=0，或者主串长度小于子串长度
	if len(mainStr) == 0 || len(mainStr) < len(subStr) {
		return -1
	}
	// 调用 BF 算法查找子串
	return bfSearch(mainStr, subStr)
}
